package com.cdream.basic.algorithm.leetcode.tree;

import java.util.LinkedHashMap;
import java.util.Map;

public class Question105 {
    Map<Integer, Integer> inorderMap = new LinkedHashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i1 = 0; i1 < preorder.length; i1++) {
            inorderMap.put(inorder[i1], i1);
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int pLeft, int pRight, int iLeft, int iRight) {
        if (preorder.length == 0) {
            return null;
        }
        if (pLeft > pRight || iLeft > iRight) {
            return null;
        }
        int root = preorder[pLeft];
        Integer inorderIndex = inorderMap.get(root);
        // 构建左侧子树
        TreeNode iLeftTree = buildTree(preorder, inorder, pLeft + 1, pLeft + (inorderIndex - iLeft), iLeft, inorderIndex - 1);

        // 构建右侧子树
        TreeNode iRightTree = buildTree(preorder, inorder, pLeft + (inorderIndex - iLeft) + 1, pRight, inorderIndex + 1, iRight);

        // 返回构建树

        return new TreeNode(root, iLeftTree, iRightTree);
    }

    public static void main(String[] args) {
        int[] i1 = new int[]{3, 9, 20, 15, 7};
        int[] i2 = new int[]{9, 3, 15, 20, 7};
        new Question105().buildTree(i1, i2);
    }
}
